Algorithm to draw circles and ellipses
This algorithm is based on the parametric form of the circle equation. For more see Parametric equation of a circle. Recall that this looks like x = h + r cosθ y = k + r sinθ where r is the radius of the circle, and h,k are the coordinates of the center. What these equation do is generate the x,y coordinates of a point on the circle given an angle θ (theta). The algorithm starts with theta at zero, and then loops adding an increment to theta each time round the loop. It draws straight line segments between these successive points on the circle. The circle is thus drawn as a series of straight lines. If the increment is small enough, the result looks like a circle to the eye, even though in strict mathematical terms is is not. The algorithm Below is the algorithm in pseudocode showing the basic idea. theta = 0; // angle that will be increased each loop h = 12 // x coordinate of circle center k = 10 // y coordinate of circle center step = 15; // amount to add to theta each time (degrees) repeat until theta >= 360; { x = h + r*cos(theta) y = k + r*sin(theta) draw a line to x,y add step to theta } The decision about how big to make the step size is a tradeoff. If it is very small, many lines will be drawn for a smooth circle, but there will be more computer time used to do it. If it is too large the circle will not be smooth and be visually ugly. Example Below is the algorithm written in Javascript using the HTML5 canvas element to draw into. var ctx = canvas.getContext("2d"); var step = 2*Math.PI/20; // see note 1 var h = 150; var k = 150; var r = 50; ctx.beginPath(); //tell canvas to start a set of lines for(var theta=0; theta < 2*Math.PI; theta+=step) { var x = h + r*Math.cos(theta); var y = k - r*Math.sin(theta); //note 2. ctx.lineTo(x,y); } ctx.closePath(); //close the end to the start point ctx.stroke(); //actually draw the accumulated lines Like most graphics systems, the canvas element differs from the usual mathematical coordinate plane: The origin is in the top left corner. The code above compensates by assuming that h, and k are actually relative to the top left. The y axis is inverted. Positive y is down the screen, not up. To correct for this, the k variable (the y coordinate of the center) must be positive to place the center some way down the screen. Also the y calculation has to subtract the sin(x) term instead of add. Marked in the code as Note 1. Note 2. The step size is set to an exact division of 2π to avoid gaps or over-runs in the circle. This code divides the circle into exactly 20 segments. Note too that as in most computer languages, the trig functions operate in radians, not degrees. 360° = 2π radians. Ellipses The circles can be made into ellipses by simply "squashing" them in one direction or the other. For an ellipse that is wider than it is tall, be divide the y coordinate by a number (here 2) to reduce its height. The two inner calculations would then look like: var x = h + r*Math.cos(theta) ; var y = k - 0.5 * r*Math.sin(theta) ; Changing the 0.5 will alter how much the vertical size is squashed. Multiply the y term this way will make an ellipse that is tall and narrow. Category:Circles Category:Math dictionary Category:Circle